#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 100
#define FLAG -100

typedef int DataType;
typedef enum bool Bool;
enum bool {
        false, true
};

struct Node {
        DataType val;
        struct Node *next;
};
typedef struct Node *PNode;

struct QNode {
        PNode front, rear;
        int len;
        int MaxSize;
};
typedef struct QNode *LinkQueue;

// eight functions:
LinkQueue createEmptyQueue_link(void);
Bool isEmptyQueue_link(LinkQueue Q);
DataType frontQueue_link(LinkQueue Q);
void enQueue_link(LinkQueue Q, DataType x);
void deQueue_link(LinkQueue Q);
LinkQueue createLinkQueue_H(void);
void print_queue(LinkQueue Q);
void destroy_queue(LinkQueue Q);

// 注：我们创建的链式队列无头结点.
LinkQueue createEmptyQueue_link(void)
{
        LinkQueue Q = (LinkQueue)malloc(sizeof(struct QNode));
        if (!Q) {
                printf("Out of memory! Can't malloc a queue!\n");
        }
        Q->MaxSize = MAX_NUM;
        Q->len = 0;
        Q->front = NULL;
        Q->rear = NULL;
        return Q;
}

Bool isEmptyQueue_link(LinkQueue Q)
{
        return Q->front == NULL;
}

DataType frontQueue_link(LinkQueue Q)
{
        if (isEmptyQueue_link(Q)) return FLAG;
        return Q->front->val;
}

// 入队尾插，出队头删.
void enQueue_link(LinkQueue Q, DataType x)
{
        // 判断队列是否满.
        if (Q->MaxSize <= Q->len) {
                printf("The queue is full now, Can't enqueue!\n");
                return ;
        }
        PNode p = (PNode)malloc(sizeof(struct Node));
        if (!p) {
                printf("Out of memory! Can't malloc a PNode to enqueue!\n");
        }
        p->val = x;
        if (Q->rear == NULL && Q->front == NULL) {
                p->next = NULL;
                Q->front = p;
        } else {
                p->next = Q->rear->next;
                Q->rear->next = p;
        }
        // 入队后，记得更新len和rear.
        Q->rear = p;
        Q->len++;
}

// 入队尾插，出队头删.
void deQueue_link(LinkQueue Q)
{
        // 判断队列是否为空.
        if (Q->len <= 0) {
                printf("The queue is empty now!Can't dequeue!\n");
                return ;
        }
        PNode tmp = Q->front;
        if (Q->rear == Q->front) {
                Q->front = Q->rear = NULL;
        } else {
                Q->front = Q->front->next;
        }
        free(tmp);
}

// 头插法创建链式队列.
LinkQueue createLinkQueue_H(void)
{
        LinkQueue head = createEmptyQueue_link();
        PNode p;
        int x;
        Bool flag = true;
        scanf("%d", &x);
        while (x != FLAG) {
                p = (PNode)malloc(sizeof(struct Node));
                p->val = x;
                // 记得更新rear成员变量的值.
                if (flag) {
                        head->rear = p;
                        flag = false;
                }
                p->next = head->front;
                head->front = p;
                head->len++;
                scanf("%d", &x);
        }
        return head;
}

void destroy_queue(LinkQueue Q)
{
        if (isEmptyQueue_link(Q)) return ;
        PNode p, q;
        PNode tmp;
        p = Q->front;
        q = Q->front;
        while (q != NULL && q->next != NULL) {
                tmp = p;
                p = p->next;
                q = q->next->next;
                free(tmp);
        }
        free(Q);
}

void print_queue(LinkQueue Q)
{
        PNode p;
        for (p = Q->front; p != NULL; p = p->next)
        {
                printf("%d ", p->val);
        }
        printf("\n");
}

int main()
{
        int x;
        printf("Please input a series number:\n");
        LinkQueue Q = createLinkQueue_H();
        if (isEmptyQueue_link(Q)) {
                printf("The queue is empty now!\n");
        } else {
                print_queue(Q);
                printf("The queue is not empty now!\n");
        }
        printf("Now, The front element is %d\n", frontQueue_link(Q));
        printf("Please input an element to enqueue: ");
        scanf("%d", &x);
        enQueue_link(Q, x);
        print_queue(Q);
        printf("Now, let's dequeue an element.\n");
        if (Q->len <= 0) {
                printf("The queue is empty now.Can't dequeue.\n");
        } else {
                deQueue_link(Q);
        }
        print_queue(Q);
        printf("Now, let's dequeue an element.\n");
        if (Q->len <= 0) {
                printf("The queue is empty now.Can't dequeue.\n");
        } else {
                deQueue_link(Q);
        }
        print_queue(Q);
        destroy_queue(Q);
        return 0;
}